#include <stdio.h>
#include <stdlib.h>
#include "bilink2.h"

typedef struct stack
{
    bintree data[100];
    int tag[100];
    int top;
} seqstack;

/**
 * 进栈
 * @param seqstack *s 栈
 * @return void
 */
void push(seqstack *s, bintree t)
{
    s->data[s->top] = t;
    s->top++;
}

bintree pop(seqstack *s)
{
    if (s->top != 0)
    {
        s->top--;
        return s->data[s->top];
    }
    else
    {

        return NULL;
    }
}

/***
 * 二叉树前序遍历非递归算法
 * @param bintree t 二叉树
 * @return void
 */
void preorder(bintree t)
{
    seqstack s;
    s.top = 0;

    while (t || s.top != 0)
    {
        if (t)
        {
            printf("%c", t->data);
            push(&s, t);
            t = t->lchild;
        }
        else
        {
            t = pop(&s);
            t = t->rchild;
        }
    }
}

/**
 * 二叉树中序遍历非递归算法
 * @param bintree t 二叉树
 * @return void
 */
void inorder(bintree t)
{
    seqstack s;
    s.top = 0;

    while (t || s.top != 0)
    {
        if (t)
        {
            push(&s, t);
            t = t->lchild;
        }
        else
        {
            t = pop(&s);
            printf("%c", t->data);
            t = t->rchild;
        }
    }
}

/**
 * 二叉树后序遍历非递归算法
 * @param bintree t 二叉树
 * @return void
 */
void postorder(bintree t)
{
    seqstack s;
    s.top = 0;

    while (t || s.top != 0)
    {
        if (t)
        {
            s.data[s.top] = t;
            s.tag[s.top] = 0;
            s.top++;
            t = t->lchild;
        }
        else
        {
            if (s.tag[s.top - 1] == 1)
            {
                s.top--;
                t = s.data[s.top];
                printf("%c", t->data);
                t = NULL;
            }
            else
            {
                s.tag[s.top - 1] = 1;
                t = s.data[s.top - 1];
                t = t->rchild;
            }
        }
    }
}